백준 2568번
오늘 풀어본 문제는 백준의 2568번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.
solved.ac 기준 CLASS
문제 정보
이 문제의 내용과 조건은 다음과 같다.
문제
두 전봇대 $A$ 와 $B$ 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다.
예를 들어, <그림 1>과 같이 전깃줄이 연결되어 있는 경우 $A$ 의 $1$ 번 위치와 $B$ 의 $8$ 번 위치를 잇는 전깃줄, $A$ 의 $3$ 번 위치와 $B$ 의 $9$ 번 위치를 잇는 전깃줄, $A$ 의 $4$ 번 위치와 $B$ 의 $1$ 번 위치를 잇는 전깃줄을 없애면 남아있는 모든 전깃줄이 서로 교차하지 않게 된다.
전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서부터 차례대로 번호가 매겨진다. 전깃줄의 개수와 전깃줄들이 두 전봇대에 연결되는 위치의 번호가 주어질 때, 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 최소 개수의 전깃줄을 구하는 프로그램을 작성하시오.
입력
첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 $100,000$ 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 $A$ 전봇대와 연결되는 위치의 번호와 $B$ 전봇대와 연결되는 위치의 번호가 차례로 주어진다. 위치의 번호는 $500,000$ 이하의 자연수이고, 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다.
출력
첫째 줄에 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 출력한다. 둘째 줄부터 한 줄에 하나씩 없애야 하는 전깃줄의 $A$ 전봇대에 연결되는 위치의 번호를 오름차순으로 출력한다. 만약 답이 두 가지 이상이라면 그 중 하나를 출력한다.
풀이과정
1번째 시도
문제에서 전깃줄이 겹치지 않는 경우를 보면, B에 연결된 위치들의 번호가 증가하는 부분수열을 이룬다는 것을 알 수 있었다. 따라서 우리가 구해야 하는 것은 LIS (최장 증가 부분 수열) 이고, 전깃줄의 개수가 $100,000$ 까지도 될 수 있으므로 $O(n \log n)$ 의 시간복잡도를 가지는 알고리즘을 이용해야 한다고 생각했다.
그리고 LIS 를 구한 뒤에는 LIS에 포함되지 않는 전깃줄들의 개수와 A에 연결된 부분의 번호들을 출력하게 하였다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
using namespace std;
struct Cord {
int start;
int end;
bool operator<(const Cord& other) const {
return (this->start < other.start);
}
};
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
cin >> n;
vector<Cord> cords;
for (int i=0; i<n; i++) {
int start, end;
cin >> start >> end;
cords.push_back({start, end});
}
sort(cords.begin(), cords.end());
vector<int> arr;
vector<int> lisIndex(n, 0);
vector<int> lis;
for (auto& cord : cords) {
arr.emplace_back(cord.end);
}
for (int i=0; i<n; i++) {
int curr = arr[i];
if (i == 0 || curr > lis.back()) {
lis.emplace_back(curr);
lisIndex[i] = lis.size() - 1;
}
else {
int index = lower_bound(lis.begin(), lis.end(), curr) - lis.begin();
lis[index] = curr;
lisIndex[i] = index;
}
}
int lisLength = lis.size();
stack<int> s;
int curr = lisLength - 1;
for (int i=n-1; curr >= 0; i--) {
if (lisIndex[i] == curr) {
s.push(arr[i]);
curr--;
}
}
cout << n - lisLength << "\n";
for (int i=0; i<n; i++) {
if (arr[i] == s.top()) {
s.pop();
}
else {
cout << cords[i].start << "\n";
}
}
return 0;
}
실행 결과 ‘런타임 에러 (Segfault)’ 가 발생하였다.
2번째 시도
Segfault 가 발생한 이유는 lisIndex 에서 인덱스 접근 과정, 마지막 출력 과정에서 스택이 비었는데 반복문이 아직 끝나지 않은 경우의 문제가 있는 것 같았다.
코드는 다음과 같이 수정하였다.
#include <bits/stdc++.h>
using namespace std;
struct Cord {
int start;
int end;
bool operator<(const Cord& other) const {
return (this->start < other.start);
}
};
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
cin >> n;
vector<Cord> cords;
for (int i=0; i<n; i++) {
int start, end;
cin >> start >> end;
cords.push_back({start, end});
}
sort(cords.begin(), cords.end());
vector<int> arr;
vector<int> lisIndex(n, 0);
vector<int> lis;
for (auto& cord : cords) {
arr.emplace_back(cord.end);
}
for (int i=0; i<n; i++) {
int curr = arr[i];
if (i == 0 || curr > lis.back()) {
lis.emplace_back(curr);
lisIndex[i] = lis.size() - 1;
}
else {
int index = lower_bound(lis.begin(), lis.end(), curr) - lis.begin();
lis[index] = curr;
lisIndex[i] = index;
}
}
int lisLength = lis.size();
stack<int> s;
int curr = lisLength - 1;
for (int i=n-1; curr >= 0; i--) {
if (lisIndex[i] == curr) {
s.push(arr[i]);
curr--;
}
}
cout << n - lisLength << "\n";
for (int i=0; i<n; i++) {
if (!s.empty() && arr[i] == s.top()) {
s.pop();
}
else {
cout << cords[i].start << "\n";
}
}
return 0;
}
그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.
마무리
예전에 LIS 문제를 풀어본 기억이 있는데, 그게 CLASS 5 였는지는 오늘 문제를 보고 알게되었다. CLASS 5 부터는 떠올리거나 이해하기 어려운 내용들이 본격적으로 나오는 것 같다…
이런 아이디어를 혼자서 떠올리고, 알고리즘을 구체화하고, 실제로 구현하고, 논문을 쓰는 등의 일을 척척 해낼 수 있으려면 앞으로 더 얼마나 공부를 많이 해야하는걸까? 세상을 넓고 배울 건 많다는 걸 다시금 느낄 뿐이다.
오늘의 PS는 여기까지!
1: https://www.acmicpc.net/problem/2568